package com.kyrie.lib_sys.utils.learn.leetCode;

import java.util.*;

/**
 * 力扣--->链表
 *
 * @author heefM
 * @date 2025-08-06
 */
public class leetCode_Node {

    public static void main(String[] args) {

        //相交链表
        // 创建链表A: 1 -> 2 -> 3 -> 4
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(2);
        headA.next.next = new ListNode(3);
        headA.next.next.next = new ListNode(4);

        // 创建链表B: 5 -> 3 -> 4 (与链表A在节点3处相交)
        ListNode headB = new ListNode(5);
        headB.next = headA.next.next; // 直接指向链表A的第3个节点(值为3)

        // 调用方法查找相交节点
        ListNode intersection = getIntersectionNode(headA, headB);
        if (intersection != null) {
            System.out.println("相交节点的值为: " + intersection.val); // 输出结果为3
        } else {
            System.out.println("两个链表不相交");
        }

        System.out.println("11111111111111111----------------------------------------------------------------------");

        // 反转链表: 1 -> 2 -> 3 -> 4 -> 5
        ListNode headC = new ListNode(1);
        headC.next = new ListNode(2);
        headC.next.next = new ListNode(3);
        headC.next.next.next = new ListNode(4);
        headC.next.next.next.next = new ListNode(5);

        // 打印原始链表
        System.out.print("原始链表: ");
        printList(headC);

        // 反转链表
        ListNode reversedHead = reverseList(headC);
        // 打印反转后的链表
        System.out.print("反转后链表: ");
        printList(reversedHead);

        System.out.println("2222222222222222----------------------------------------------------------------------");

        //回文链表判断
        ListNode headD = new ListNode(1);
        headD.next = new ListNode(2);
        headD.next.next = new ListNode(3);
        headD.next.next.next = new ListNode(2);
        headD.next.next.next.next = new ListNode(1);

        System.out.println(isPalindrome(headD));

        System.out.println("3333333333333333----------------------------------------------------------------------");

        //合并两个有序链表
        System.out.println(mergeTwoLists(headA, headB));


        System.out.println("444444444444444444----------------------------------------------------------------------");


        //  两数相加
        ListNode headE = new ListNode(1);
        headE.next = new ListNode(2);
        headE.next.next = new ListNode(4);

        System.out.println(addTwoNumbers(headE, headE));

        System.out.println("5555555555555----------------------------------------------------------------------");

        //删除倒数第n个节点
        ListNode headF = new ListNode(1);
        headF.next = new ListNode(2);
        headF.next.next = new ListNode(5);

        System.out.println(removeNthFromEnd(headF, 2));
        System.out.println("66666666666------------------------------------------------------------");


        //两两交换链表中的节点
        ListNode headG = new ListNode(1);
        headE.next = new ListNode(2);
        headE.next.next = new ListNode(3);

        ListNode headH = new ListNode(4);
        headE.next = new ListNode(1);
        headE.next.next.next = new ListNode(5);
        System.out.println("777777777777------------------------------------------------------------");


        //两两交换其中相邻的节点，并返回交换后链表的头节点
    }

    /**
     * 打印链表中的所有值
     *
     * @param head 链表头节点
     */
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println(); // 换行
    }

    /**
     * 1:相交链表;
     *
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashMap<Object, Object> map = new HashMap<>();

        // 将链表A的所有节点存入HashMap
        ListNode currentA = headA;
        while (currentA != null) {
            map.put(currentA, null);
            currentA = currentA.next;
        }

        // 遍历链表B，检查是否有节点在HashMap中
        ListNode currentB = headB;
        while (currentB != null) {
            if (map.containsKey(currentB)) {
                return currentB;
            }
            currentB = currentB.next;
        }
        return null;
    }

//////////////////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * 2:反转链表;
     *
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode next;
        while (head != null) {
            next = head.next; // 保存下一个节点(保存下一个)  next=2 单纯的就是变量的值
            head.next = prev; // 当前节点 {指向} 前一个节点(将当前节点指向下一个节点)
            prev = head;      // 更新prev为当前节点(将当前节点指向前一个) 单纯就是变量的值
            head = next;      // 移动到下一个节点 变化当前节点;
        }
        return prev;
    }

    /**
     * 3:回文链表
     *
     * @param head
     * @return
     */
    public static boolean isPalindrome(ListNode head) {

        // 用ArrayList替代LinkedList，优化随机访问性能
        List<ListNode> list = new ArrayList<>();

        // 将所有节点存入列表
        ListNode current = head;
        while (current != null) {
            list.add(current);
            current = current.next;
        }

        // 双指针比较：头指针和尾指针向中间移动
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            // 比较对应位置的节点值
            if (list.get(left).val != list.get(right).val) {
                return false;
            }
            left++;
            right--;
        }
        return true;

    }

    /**
     * 4:环形链表
     *
     * @param head
     * @return
     */
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head; //统一起点

        if (head == null) {
            return false;
        }
        while (fast.next != null && fast.next.next != null && fast.next.next.next != null) {
            fast = head.next.next.next; //快的先走两步
            if (fast == slow) {
                return true;
            }
            slow = head.next;  //慢的走一步
            if (slow == fast) {
                return true;
            }

        }
        return false;
    }

    /**
     * 6:合并两个有序链表
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> list = new ArrayList<>();

        //遍历链表1
        while (l1 != null) {
            list.add(l1.val);
            if (l1 != null) {
                l1 = l1.next;
            }
        }
        //遍历链表2
        while (l2 != null) {
            list.add(l2.val);
            if (l2 != null) {
                l2 = l2.next;
            }

        }
        //排序
        Collections.sort(list);
        //定义一个新链表,初始化为0
        ListNode newListNode = new ListNode(0);
        ListNode temp = newListNode;
        for (Integer val : list) {
            //赋值
            temp.next = new ListNode(val);
            //移动
            temp = temp.next;
        }
        return newListNode.next;

    }

    /**
     * 7:链表两数之和
     *
     * @param l1
     * @param l2
     * @return
     */

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //1.创建一个链表节点
        ListNode root = new ListNode(0);
        //2.创建一个副本(防止原空间被重置)
        ListNode sum = root;
        //3.进位
        int adds = 0;

        //4.进位为0,或者最长链表为空
        while (l1 != null || l2 != null || adds != 0) {

            //5.记录两个链表之和的值
            int currV = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + adds;
            if (currV > 9) {
                currV -= 10;
                adds = 1;
            } else {
                adds = 0;
            }
            //6.创建一个节点,并赋值  记录两个链表之和的值,存入链表
            sum.next = new ListNode(currV); //7->8->9
            //7.移动链表和的位置
            sum = sum.next;

            //8.移动两个链表位置
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }

        }
        return root.next;
    }

    /**
     * 8:删除链表的倒数第N个节点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {

        //1.遍历链表,获取值,存入数组
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        ListNode newHead = head;
        while (newHead != null) {

            newHead = newHead.next;
        }
        return head;
    }

    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        //1.初始化分配一个新节点
        ListNode newHead = new ListNode(0, head);

        //2.定义快指针.遍历链表,通过快指针找到需要删除节点的前一个节点
        ListNode first = newHead;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }

        //3.定义慢指针.遍历链表,通过慢指针找到需要删除节点的后一个节点
        ListNode slow = newHead;
        while (first.next != null) {
            slow = slow.next;
            first = first.next;
        }
        slow.next = slow.next.next; //删除节点(找到需要删除节点的前一个节点和后一个节点)
        return newHead.next;
    }

    /**
     * 两两交换链表节点
     */
    public static ListNode swapPairs(ListNode head) {
        return null;
    }

    /**
     * 定义链表节点类
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 5:环形链表|| (要找出相遇点并且返回)
     *
     * @return
     */
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            while (true) {
                if (fast.next == null || fast.next.next == null) {
                    return null;
                }
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) {
                    break;
                }
            }  //判断是否相交, 将快指针存以相交点作为起点
            slow = head; //将满指针置为链表第一个
            while (true) {
                if (slow == fast) {
                    return fast;
                }//当他们相遇的时候就能找到这个点,直接返回;
                slow = slow.next;
                fast = fast.next;
            }

        }
    }

}


//    /**
//     * 回文链表判断;
//     * @param head
//     * @return
//     */
//    public static boolean isPalindrome(ListNode head) {
//        int count = 0;
//        ListNode curr = head;
//        while (curr != null) {
//            count++;
//            curr = curr.next;
//        }
//        count = count / 2;
//        curr = head;
//        while (count-- > 0) {
//            count--;
//            curr = curr.next;
//        }
//        ListNode reverse = reverseList(curr);
//        while (reverse != null) {
//            if (reverse.val != head.val) {
//                return false;
//            }
//            reverse = reverse.next;
//            head = head.next;
//        }
//
//        return true;
//    }



